/*-----------------------------------------------------------------------------
 * File Name ..... parheap.c
 *
 * Purpose ....... Contains functions for performing the insert delete cycles
 *                 of the parallel heap
 *
 * Functions ..... PerformInsertDelete, UpdateProcesses, DeleteUpdate,
 *                 InsertUpdate, ParHeapSatisfiedAt, AppendToParHeap,
 *                 GetSubstituteItems, FetchInsertItems, GoBackByOneNode,
 *                 SetLastLevels, IsLeafNode, GetItemsFromHeap,
 *                 ParGetInsertItems
 *
 * Date Written .. April 28, 1993
 *
 * Modification History
 *    Author            Date                          Purpose
 *    ------            ----                          -------
 * Sagar Sawant       April 28, 1993    The original version of parheap.c
 * Sagar Sawant       Nov 2, 1993       Changed to incorporate:
 *                                      1. New Heap structure instead of int
 *                                         Added the functions
 *                                         GetItemsFromHeap
 *                                      2. Parallel step 2. Added the function
 *                                         ParGetInsertItems
 * Dinesh Agarwal     July 12, 2009     Ported the earlier version using PThreads.
 *---------------------------------------------------------------------------*/


/*-------------------------- Include Files ----------------------------------*/
#define _GNU_SOURCE
#include <sched.h>
#include <sys/syscall.h>
#include <sys/types.h>
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>
#include <sys/times.h>
#include <sys/time.h>

#include <sys/param.h>
#include <unistd.h>
#include <sys/syscall.h>
#include <pthread.h>
#include "parheap.h"
#include "pardef.h"
#include <errno.h>
/*-------------------------- #defines ----------------------------------------*/
#define ODD            1
#define EVEN           0
#define min( a, b ) ( ((a) < (b)) ? (a) : (b) )



/*-------------------------- Extern Variables -------------------------------*/
extern double total;
extern PARHEAP ***ParHeap;
extern int M;
/* extern int ***ParHeap;  */         /* Parallel Heap of the form  */
extern LevelFlagType *LevelFlag; /* One LevelFlag per level of ParHeap */
extern int LastLevel1;           /* Last level of heap excluding insert items */
struct timeval myTVstart, myTVend;
extern int LastNode1;            /* Last node of heap excluding insert items */
extern int NoOfLastItems1;       /* No. of items int last node of heap */
/* excluding insert items */
extern int LastLevel;            /* Last level of heap including insert items */
extern int LastNode;             /* Last node of heap including insert items */
extern int NoOfLastItems;        /* No. of items int last node of heap */
extern long magicTime;
extern PARHEAP *DeletedItems; /* including insert items */
extern PARHEAP *NewItems;      /* New insert items */
extern int r;                    /* No. of items in one node */
extern pthread_barrier_t Maintenance_Barrier;/* Barrier */
extern pthread_barrier_t Barrier_PMinus1;
extern pthread_barrier_t WorkerWithP0_Barrier;
extern pthread_barrier_t Sync_Barrier;

extern pthread_barrier_t Worker_Barrier;
extern pthread_mutex_t PT_mutex;
extern Prefetch_data *pfd;
extern PARHEAP *partmp;
/*---------------------------Extern Functions -------------------------------*/
extern void PH_GetNewSortedItems(int n, int startelem, long  maxvalue, PARHEAP *ParItems);
extern void PrintParHeap(FILE *outfile);
extern void PrintPHArray(FILE *, PARHEAP *, int);
extern int ParHeapCmp(const void *elem1, const void *elem2);
extern void *MyMalloc(int);
extern void *MyCalloc(int);
extern void ParSortNewItems(int,int);
extern void mergemin(PARHEAP *, int, PARHEAP *,int, PARHEAP *);
extern void mergemax(PARHEAP *,  PARHEAP *,PARHEAP *, int);
extern int Get_Nth_Bit_From_Right(int,int);
extern void ExpandParHeap();
extern int ceil_log2(int);
extern void PH_Merge();
extern double my_difftime ();
/*--------------------------------- Functions -------------------------------*/
void *PerformInsertDelete(void *threadargs);
void UpdateProcesses(int OddOrEven, int NoOfProcesses,int proc_id);
void UpdateProcessesChunk(int OddOrEven, int NoOfProcesses,int proc_id);
void UpdateProcessesCycle(int OddOrEven, int NoOfProcesses, int proc_id, int start);
void DeleteUpdate(int CurrentLevel,int proc_id, int NoOfProcesses);
void InsertUpdate(int OddOrEven,int FlagType,int CurrentLevel,int proc_id);
int ParHeapSatisfiedAt(int CurrentLevel,int CurrentNode);
void AppendToParHeap(PARHEAP *Items, int num);
void GetSubstituteItems(int num,PARHEAP *Items);
int FetchInsertItems(int CurrentLevel,int FlagType,int OddOrEven,int *InsertLevel,int *InsertNode,int *InsertOffsetInNode,int *NoOfInsertItems);
void GoBackByOneNode();
void SetLastLevels();
int IsLeafNode(int CurrentLevel, int CurrentNode);
int *GetItemsFromHeap(PARHEAP *HeapItems,int num);
void ParGetInsertItems(PARHEAP *InsertItems,int NoOfInsertItems,int NoOfProcesses,int MyId);
void *Prefetch(void *pfdata);

/*------------------------------- Global Variables ---------------------------*/
int Ins_NoOfLastItems;       /* No. of last items - used by */
int ParHeapCntr;
#ifdef PF
void *Prefetch(void *pfdata)
{
     Prefetch_data *my_pfd;
     //PARHEAP *PrePar;
     int id;
     PARHEAP *PrePar = (PARHEAP *) MyMalloc(2 * r * sizeof(PARHEAP));
     cpu_set_t cpu;
     /*for each thread id is similar to my_id*/
     my_pfd = (Prefetch_data *) pfdata;
     id = my_pfd->tid;
     CPU_ZERO(&cpu);
     CPU_SET(id % CORES, &cpu);
     sched_setaffinity(syscall(SYS_gettid), sizeof(cpu_set_t), &cpu);
     while(my_pfd->spin != NO_SPIN) 
     {
         pthread_mutex_lock(&(my_pfd->mutex));
         pthread_cond_wait(&(my_pfd->cond), &(my_pfd->mutex));
         if ( my_pfd->temp[1]>= 0)   
         {
             memcpy(PrePar, &partmp[HEAPINDEX(my_pfd->temp[0],my_pfd->temp[1],0,r)], r * sizeof(PARHEAP));
             memcpy(&PrePar[r], &partmp[HEAPINDEX(my_pfd->temp[0],my_pfd->temp[1],r,r)], r * sizeof(PARHEAP));
         }
         pthread_mutex_unlock(&(my_pfd->mutex));
     }
     pthread_exit(NULL);
}
#endif
/*----------------------------------------------------------------------------
 * Function ........... PerformInsert
 *
 * Purpose ............ The outer loop for performing the insert-delete cycles.
 *
 * Arguments Passed ... NoOfInsertDeleteCycles - No. of time the loop is to be
 *                                               executed
 *                      NoOfProcesses - No of threads to be forked.
 *                      RandomK - a random number to decide the priority of
 *                                the new items to be inserted into the heap.
 *                      ToBeDeleted - No of items to be deleted in each cycle.
 *                      ToBeInserted - No of items to be inserted in each cycle.
 *                        ThreadID - id of the thread.
 *
 * Return Value ....... None
 *
 * Globals Modified ... Barrier1, ParHeap
 *---------------------------------------------------------------------------*/
void *PerformInsertDelete(void *threadargs)
{
    int i = 0, k = 0, NoLeftover=0, start;
    PARHEAP *Leftovers, *Temp;
    int my_id=-1;
    THREAD_DATA *my_data;
    my_data = (THREAD_DATA *) threadargs;
    my_id = my_data->taskid;
    int NoOfInsertDeleteCycles = my_data->NoOfInsertDeleteCycles;
    int NoOfProcesses = my_data->NoOfProcesses;
    int ToBeDeleted =  my_data->ToBeDeleted;
    int ToBeInserted = my_data->ToBeInserted;

    if (my_id == 0) 
    {
       Leftovers = (PARHEAP *) MyMalloc(3 * r * sizeof(PARHEAP));
       Temp = (PARHEAP *) MyMalloc(2 * r * sizeof(PARHEAP));
    }

    cpu_set_t cpu;
    CPU_ZERO(&cpu);
    CPU_SET(my_id % CORES, &cpu);
    sched_setaffinity(syscall(SYS_gettid), sizeof(cpu_set_t), &cpu);
  
    start = 0;
    k = ToBeInserted;

    /*--------- Main loop starts here -----------*/
    for ( i=0 ; i < NoOfInsertDeleteCycles ; i++)
    {
#ifdef RELAXED_HOLD
        k = rand() % ( 2 * ToBeDeleted + 1);    
#endif
        /* STEP 1 starts here */
#ifdef HDEBUG
        fprintf(stdout, "PerformInsertDelete: Entered for loop, cycle - %d\n", i);
        fprintf(stdout, "--------------------STEP 1 starts-------------------\n");
#endif

        /* To use PPQ in an application this should go to the end */
        if (my_id < M)
        {
#ifdef ROUNDROBIN
            UpdateProcesses(ODD, NoOfProcesses, my_id);
#elif BLOCKING
            UpdateProcessesChunk(ODD, NoOfProcesses, my_id);
#else
            UpdateProcessesCycle(ODD, NoOfProcesses, my_id, start);
            start += 2;
            if (start >= LastLevel1) start = start % (LastLevel1);
#endif
        }

#ifdef HDEBUG
        fprintf(stdout, "STEP 1 over and Parallel heap now is \n");
        PrintParHeap(stdout);
#endif

        /* STEP 2 starts here */
#ifdef HDEBUG
        fprintf(stdout, "--------------------STEP 2 starts-------------------\n");
#endif

        if (NoOfProcesses != 1)
        {
            /* everybody synchronizes here */
            int rc;
            rc = pthread_barrier_wait(&Sync_Barrier);
            if (rc != 0 && rc != PTHREAD_BARRIER_SERIAL_THREAD)
            {
                printf("Could not wait on the barrier\n");
                exit(-1);
            }
        }

#ifdef HDEBUG
        fprintf(stdout, "No. of items to be inserted, k = %d\n", k);
#endif
        /* If there are items to be inserted */
        if (k > 0)
        {
            if (my_id == 0)    /* Only 1 processor should execute steps 2 & 3 */
            {
#ifdef HDEBUG
                fprintf(stdout, "Newly created Items = ");
                PrintPHArray(stdout, NewItems, k);
                fprintf(stdout, "\n");
#endif
                /* Merge new items with the items at root */
                PH_Merge(partmp, r, NewItems, k, DeletedItems);
                NoLeftover = r + k - ToBeDeleted;
                /* After this merging delete the items to be deleted and leave the rest in Leftovers */
                memcpy(Leftovers, &DeletedItems[ToBeDeleted],(NoLeftover)*sizeof(PARHEAP));
#ifdef HDEBUG
                fprintf(stdout, "Leftovers = ");
                PrintPHArray(stdout, Leftovers, NoLeftover);
                fprintf(stdout, "\n");
#endif
            }
        }
        else /* There is nothing to be inserted */
        {
            if (my_id == 0)    /* Only 1 processor should execute step 2 */
            {
                memcpy(DeletedItems, partmp, (ToBeDeleted*sizeof(PARHEAP)) );
                NoLeftover = r-ToBeDeleted;
                /* if not everything was deleted from root */
                if (!NoLeftover)
                {
                    memcpy(Leftovers, &(partmp[ToBeDeleted].item), (NoLeftover)*sizeof(PARHEAP));
                }
#ifdef HDEBUG
                fprintf(stdout, "No new items generated");
                fprintf(stdout, "Leftovers = ");
                PrintPHArray(stdout, Leftovers, NoLeftover);
                fprintf(stdout, "\n");
#endif
            }
        }

        if ((NoOfProcesses > M) && ((my_id == 0) || (my_id >= M)))
        {
            int rc;
            rc = pthread_barrier_wait(&WorkerWithP0_Barrier);
            if (rc != 0 && rc != PTHREAD_BARRIER_SERIAL_THREAD)
            {
                printf("Could not wait on barrier\n");
                exit(-1);
            }
            if (my_id >= M)
            {
                ParGetInsertItems(NewItems, k, NoOfProcesses, my_id);
            }
        }

        if (my_id == 0)    /* Only 1 processor should execute step 3 */
        {
            /* STEP 3 starts here */
            if (k >= ToBeDeleted)
            {
                /* Place smallest r of the leftovers into the root as substitute items */
                memcpy(partmp, Leftovers, r*sizeof(PARHEAP));
                if (k > ToBeDeleted) 
                {
                    AppendToParHeap(&Leftovers[r], NoLeftover-r);
                }
                /* Place the remaining NoLeftover-r items at the end of the heap as insert items */
            }
            else
            {
                GetSubstituteItems(ToBeDeleted-k, Temp);
                PH_Merge(Temp, ToBeDeleted-k, Leftovers, NoLeftover, partmp);
            }
            if ( !ParHeapSatisfiedAt(0, 0) )
                LevelFlag[0].delete_flag = 0;
        }

#ifdef HDEBUG
            fprintf(stdout, "STEP 3 over and Parallel heap now is \n");
            PrintParHeap(stdout);
#endif
        if ((NoOfProcesses != 1) && (my_id <M))
        {
            int rc;
            rc = pthread_barrier_wait(&Maintenance_Barrier);
            if (rc != 0 && rc != PTHREAD_BARRIER_SERIAL_THREAD)
            {
                printf("Could not wait on barrier\n");
                exit(-1);
            }
        }


        /* STEP 4 starts here */
#ifdef HDEBUG
        fprintf(stdout, "--------------------STEP 4 starts-------------------\n");
#endif

        /* every body participates */
        if (NoOfProcesses == M)
            ParGetInsertItems(NewItems, k, NoOfProcesses, my_id);

        if (my_id < M)
        {
#ifdef ROUNDROBIN
            UpdateProcesses(EVEN, NoOfProcesses, my_id);
#elif BLOCKING
            UpdateProcessesChunk(EVEN, NoOfProcesses, my_id);
#else
            UpdateProcessesCycle(EVEN, NoOfProcesses, my_id, start);
#endif
        }

        if ((NoOfProcesses != 1) && (my_id <M))
        {
            int rc;
            rc = pthread_barrier_wait(&Maintenance_Barrier);
            if (rc != 0 && rc != PTHREAD_BARRIER_SERIAL_THREAD)
            {
                printf("Could not wait on barrier\n");
                exit(-1);
            }
        }


#ifdef HDEBUG
        fprintf(stdout, "STEP 4 over and Parallel heap now is \n");
        PrintParHeap(stdout);
#endif
    }
#ifdef PF
    pthread_mutex_lock(&pfd[my_id].mutex);
    pfd[my_id].spin=NO_SPIN;
    pthread_cond_signal(&pfd[my_id].cond);
    pthread_mutex_unlock(&pfd[my_id].mutex);
#endif
    pthread_exit(NULL);
}


/*----------------------------------------------------------------------------
 * Function ........... UpdateProcesses
 *
 * Purpose ............ Assigns levels to the processors and then calls
 *                      DeleteUpdate and InsertUpdate
 *
 * Arguments Passed ... OddOrEven - ODD or EVEN update
 *                      NoOfProcesses - No. of processes forked
 *
 * Return Value ....... None
 *
 * Globals Modified ... None
 *---------------------------------------------------------------------------*/
 void UpdateProcessesCycle(int OddOrEven, int NoOfProcesses, int proc_id, int start)
{
    int CurrentLevel, CurrentNode, StartLevel;
    int i , crossed = 0;
    CurrentLevel =  (OddOrEven == ODD) ? (2 * proc_id) + 1 : (2 * proc_id) ;
    CurrentLevel += start;
    NoOfProcesses = M;
    StartLevel = CurrentLevel - NoOfProcesses * proc_id ;
    while( (crossed == 0 && CurrentLevel < LastLevel1) || ( (crossed == 1) && (CurrentLevel < StartLevel) ))
    {
        //printf("id %d level %d\n",proc_id, CurrentLevel);
        CurrentNode = LevelFlag[CurrentLevel].delete_flag;
        /* Initial Node where deleteupdate process begins */
        if (CurrentNode != -1)
        {
            DeleteUpdate(CurrentLevel, proc_id, NoOfProcesses);
        }
        for (i=0; i < MAX_INSERTS; i++)
        {
            if (LevelFlag[CurrentLevel].Inserts[i].insert_flag != -1)
            {
                InsertUpdate(OddOrEven, i, CurrentLevel,proc_id);
            }
        }
        CurrentLevel = CurrentLevel + (2 * NoOfProcesses);
        if (CurrentLevel >= LastLevel1 )
        {
            CurrentLevel = CurrentLevel % LastLevel1;
            crossed = 1;
        }
    }
}
void UpdateProcessesChunk(int OddOrEven, int NoOfProcesses, int proc_id)
{
    int CurrentLevel, MaxLevel;
    int i, r;
    r = LastLevel1 % M;
    NoOfProcesses = M;
    CurrentLevel = proc_id * (floor(LastLevel1 / M)) + min(proc_id,r);
    MaxLevel = (proc_id + 1) * (floor(LastLevel1 / M)) + min(proc_id + 1,r) - 1;

    if (OddOrEven == ODD)
    {
        if (CurrentLevel % 2 == 0)
        {
            CurrentLevel++;
        }
    }
    else
    {
        if (CurrentLevel % 2 == 1)
        {
            CurrentLevel++;
        }
    }

    while (CurrentLevel <= MaxLevel)
    {
        /* Initial Node where deleteupdate process begins */
        int CurrentNode = LevelFlag[CurrentLevel].delete_flag;
        if (CurrentNode != -1)
        {
            DeleteUpdate(CurrentLevel,proc_id, NoOfProcesses);
        }
        for ( i=0 ; i<MAX_INSERTS ; i++ )
        {
            if (LevelFlag[CurrentLevel].Inserts[i].insert_flag != -1)
            {
                InsertUpdate(OddOrEven, i, CurrentLevel,proc_id);
            }
        }
        CurrentLevel = CurrentLevel + 2;
    }
}

void UpdateProcesses(int OddOrEven, int NoOfProcesses, int proc_id)
{
    int CurrentLevel;
    int i;
    NoOfProcesses = M;
    CurrentLevel =  (OddOrEven == ODD) ? (2 * proc_id) + 1 : (2 * proc_id) ;

    while (CurrentLevel <= LastLevel1)
    {
        int CurrentNode = LevelFlag[CurrentLevel].delete_flag;/* Initial Node where deleteupdate process begins */
        if (CurrentNode != -1)
        {
            DeleteUpdate(CurrentLevel, proc_id, NoOfProcesses);
        }
        for (i=0; i < MAX_INSERTS; i++)
        {
            if (LevelFlag[CurrentLevel].Inserts[i].insert_flag != -1)
            {
                InsertUpdate(OddOrEven, i, CurrentLevel,proc_id);
            }
        }

        CurrentLevel = CurrentLevel + (2 * NoOfProcesses);
    }
}


/*----------------------------------------------------------------------------
 * Function ........... DeleteUpdate
 *
 * Purpose ............ Carries out the delete update process on one level
 *                      of the heap.
 *
 * Arguments Passed ... CurrentLevel - Level on which delete update is to be
 *                      performed
 *
 * Return Value ....... None
 *
 * Globals Modified ... ParHeap, LevelFlag
 *---------------------------------------------------------------------------*/
void DeleteUpdate(int CurrentLevel,int proc_id, int NoOfProcesses)
{
    int CurrentNode, x, y, z, x1, y1;
    int CurrentIndex, RightChildIndex, LeftChildIndex;
    //PARHEAP Temp1[2*MAXITEMS], Temp2[3*MAXITEMS];
    PARHEAP *Temp1, *Temp2;
    Temp1 = (PARHEAP *) MyMalloc(2 * r * sizeof(PARHEAP));
    Temp2 = (PARHEAP *) MyMalloc(3 * r * sizeof(PARHEAP));
    CurrentNode = LevelFlag[CurrentLevel].delete_flag;
    LevelFlag[CurrentLevel].delete_flag = -1;          /* Reset delete flag */
    if (!IsLeafNode(CurrentLevel, CurrentNode) )
    {
        if ( (CurrentLevel < (LastLevel1 - 1)) || ( (CurrentLevel == (LastLevel1 - 1)) && ( ((2*CurrentNode + 1) < LastNode1) || (((2*CurrentNode + 1) == LastNode1) && (NoOfLastItems1 == r)))))
        {
            CurrentIndex = HEAPINDEX((CurrentLevel+1), (2 * CurrentNode), r-1, r);
            RightChildIndex = (CurrentIndex + r) * 2;

            //x = ParHeap[CurrentLevel+1][2*CurrentNode][r-1].item;
            x = partmp[CurrentIndex].item;
            /* largest item of of left child    */
            //x1 = ParHeap[CurrentLevel+1][2*CurrentNode][0].item;
            x1 = partmp[CurrentIndex-r+1].item;
            /* x1=smallest item */
            /* of left child    */
            //y = ParHeap[CurrentLevel+1][2*CurrentNode+1][r-1].item;
            y = partmp[HEAPINDEX((CurrentLevel+1), (2*CurrentNode+1),(r-1),r)].item;
            /* y=largest item */
            /* of right child */
            //y1 = ParHeap[CurrentLevel+1][2*CurrentNode+1][0].item;
            y1 = partmp[HEAPINDEX((CurrentLevel+1), (2*CurrentNode+1),0,r)].item;
            /* y1=smallest item*/
            /* of right child  */
            //z = ParHeap[CurrentLevel][CurrentNode][r-1].item;
            z = partmp[HEAPINDEX(CurrentLevel, (2*CurrentNode),(r-1),r)].item;
            /* z = largest item of  */
            /* current node         */
            if (z <= x1)
            {
                if (z <= y1)
                {
                    /* No need for delete to continue */
                    return;
                }
                else
                {

                    CurrentIndex = HEAPINDEX(CurrentLevel, CurrentNode, 0, r);
                    RightChildIndex = (CurrentIndex + r) * 2;
                    mergemin(&(partmp[CurrentIndex]), r, &(partmp[RightChildIndex]), r, Temp1);
                    memcpy(&(partmp[RightChildIndex]), Temp1, r*sizeof(PARHEAP));
                    LevelFlag[CurrentLevel+1].delete_flag = 2 * CurrentNode + 1;/*This is the new currentnode*/
#ifdef PF
                    int LeveltoPF = CurrentLevel+2;
                    if (LeveltoPF < LastLevel1)  
                    {
                        int NodetoPF1 = 2 * (2 * CurrentNode + 1);
                        //printf("Level %d Node %d\n", LeveltoPF, NodetoPF1);
                        //int proc_id = min(floor((LeveltoPF)/(floor(LastLevel1/M)+1)),floor((LeveltoPF-(LastLevel1%M))/(floor(LastLevel1/M))));
                        //int proc_id = (LeveltoPF % NoOfProcesses)/2;
                        /* Triggering prefetching threads*/ 
                        pthread_mutex_lock(&(pfd[proc_id].mutex));
                        pfd[proc_id].temp[0] = LeveltoPF;
                        pfd[proc_id].temp[1] = NodetoPF1;
                        pthread_cond_signal(&(pfd[proc_id].cond));
                        pthread_mutex_unlock(&(pfd[proc_id].mutex));
                    } 
#endif
                }
            }
            else if (z <= y1)
            {
                CurrentIndex = HEAPINDEX(CurrentLevel, CurrentNode, 0, r);
                LeftChildIndex = CurrentIndex * 2 + r;
                LevelFlag[CurrentLevel+1].delete_flag = 2*CurrentNode;
                mergemin(&(partmp[CurrentIndex]), r, &(partmp[LeftChildIndex]), r, Temp1);
                memcpy(&(partmp[LeftChildIndex]), Temp1, r*sizeof(PARHEAP));
#ifdef PF
                int LeveltoPF = CurrentLevel+2;
                if (LeveltoPF < LastLevel1)  /* >0 because added +1 in calculation*/
                {
                    int NodetoPF1 = 2 * (2 * CurrentNode);
                    //printf("Level %d Node %d\n", LeveltoPF, NodetoPF1);

                    //int proc_id = min(floor((LeveltoPF)/(floor(LastLevel1/M)+1)),floor((LeveltoPF-(LastLevel1%M))/(floor(LastLevel1/M))));
                    //int proc_id = (LeveltoPF % NoOfProcesses)/2;
                    pthread_mutex_lock(&(pfd[proc_id].mutex));
                    pfd[proc_id].temp[0] = LeveltoPF;
                    pfd[proc_id].temp[1] = NodetoPF1;
                    pthread_cond_signal(&(pfd[proc_id].cond));
                    pthread_mutex_unlock(&(pfd[proc_id].mutex));
                }
#endif  
            }
            else
            {
                if ( y >= x)
                {
                    CurrentIndex = HEAPINDEX(CurrentLevel, CurrentNode, 0, r);
                    RightChildIndex = (CurrentIndex + r) * 2 ;
                    LeftChildIndex = RightChildIndex - r;
                    mergemax(&(partmp[LeftChildIndex]), &(partmp[RightChildIndex]), Temp1, r);
                    mergemin(&(partmp[CurrentIndex]), r, Temp1, r, &(partmp[LeftChildIndex]));
                    LevelFlag[CurrentLevel+1].delete_flag = 2*CurrentNode;
#ifdef PF 
                    int LeveltoPF = CurrentLevel+2;
                    if (LeveltoPF < LastLevel1 )  /* >0 because added +1 in calculation*/
                    {
                        int NodetoPF1 = 2 * (2 * CurrentNode);
                        //printf("Level %d Node %d\n", LeveltoPF, NodetoPF1);
                        /* Triggering prefetching threads*/ 
                        //int proc_id = min(floor((LeveltoPF)/(floor(LastLevel1/M)+1)),floor((LeveltoPF-(LastLevel1%M))/(floor(LastLevel1/M))));
                        //int proc_id = (LeveltoPF % NoOfProcesses)/2;
                        pthread_mutex_lock(&(pfd[proc_id].mutex));
                        pfd[proc_id].temp[0] = LeveltoPF;
                        pfd[proc_id].temp[1] = NodetoPF1;
                        pthread_cond_signal(&(pfd[proc_id].cond));
                        pthread_mutex_unlock(&(pfd[proc_id].mutex));
                    } 
#endif
                }
                else
                {
                    CurrentIndex = HEAPINDEX(CurrentLevel, CurrentNode, 0, r);
                    RightChildIndex = (CurrentIndex + r) * 2 ;
                    LeftChildIndex = RightChildIndex - r;
                    mergemax(&(partmp[RightChildIndex]), &(partmp[LeftChildIndex]), Temp1, r);
                    mergemin(&(partmp[CurrentIndex]), r, Temp1, r, &(partmp[RightChildIndex]));
                    LevelFlag[CurrentLevel+1].delete_flag = 2*CurrentNode+1;
#ifdef PF
                    int LeveltoPF = CurrentLevel+2;
                    if (LeveltoPF < LastLevel1)  /* >0 because added +1 in calculation*/
                    {
                        int NodetoPF1 = 2 * (2 * CurrentNode + 1);
                        //printf("Level %d Node %d\n", LeveltoPF, NodetoPF1);
                        /* Triggering prefetching threads*/ 
                        //int proc_id = min(floor((LeveltoPF)/(floor(LastLevel1/M)+1)),floor((LeveltoPF-(LastLevel1%M))/(floor(LastLevel1/M))));
                        //int proc_id = (LeveltoPF%NoOfProcesses)/2;
                        pthread_mutex_lock(&(pfd[proc_id].mutex));
                        pfd[proc_id].temp[0] = LeveltoPF;
                        pfd[proc_id].temp[1] = NodetoPF1;
                        pthread_cond_signal(&(pfd[proc_id].cond));
                        pthread_mutex_unlock(&(pfd[proc_id].mutex));
                    } 
#endif
                }
            }
        }
        else if ( (CurrentLevel == (LastLevel1 - 1)) && (( (2*CurrentNode + 1) == LastNode1) && (NoOfLastItems1 < r) ) )
            /* Right child exists and has items LESS THAN r */
        {
            CurrentIndex = HEAPINDEX(CurrentLevel, CurrentNode, 0, r);
            RightChildIndex = (CurrentIndex + r) * 2 ;
            LeftChildIndex = RightChildIndex - r;
            /* Merge the current node with its 2 children */
            PH_Merge(&(partmp[CurrentIndex]), r, &(partmp[LeftChildIndex]), r, Temp1);
            PH_Merge(&(partmp[RightChildIndex]), NoOfLastItems1, Temp1, 2*r, Temp2);

            /* Place the smallest r items into Current Node */
            memcpy(&(partmp[CurrentIndex]), Temp2, r * sizeof(PARHEAP));
            memcpy(&(partmp[LeftChildIndex]),&Temp2[r], r*sizeof(PARHEAP));
            memcpy(&(partmp[RightChildIndex]), &Temp2[2*r], NoOfLastItems1*sizeof(PARHEAP));
        }
        else         /* right child does not exist */
        {
            CurrentIndex = HEAPINDEX(CurrentLevel, CurrentNode, 0, r);
            RightChildIndex = (CurrentIndex + r) * 2 ;
            LeftChildIndex = RightChildIndex - r;
            /* PH_Merge the current node with its left child */
            PH_Merge(&(partmp[CurrentIndex]), r, &partmp[LeftChildIndex], NoOfLastItems1, Temp1);
            memcpy(&partmp[CurrentIndex], Temp1, r * sizeof(PARHEAP));
            memcpy(&partmp[LeftChildIndex], &Temp1[r], NoOfLastItems1*sizeof(PARHEAP));
        }
    }
    free(Temp1); free(Temp2);
        
}


/*----------------------------------------------------------------------------
 * Function ........... InsertUpdate
 *
 * Purpose ............ Carries out the insert update process on one level
 *                      of the heap.
 *
 * Arguments Passed ... OddOrEven - ODD or EVEN level update
 *                      FlagType - INSERT_FLAG1 or INSERT_FLAG2
 *                      CurrentLevel - Level on which insert update is to be
 *                      performed
 *
 * Return Value ....... None
 *
 * Globals Modified ... ParHeap, LevelFlag, LastLevel1, LastNode1,
 *                      NoOfLastItems1
 *---------------------------------------------------------------------------*/
void InsertUpdate(int OddOrEven, int FlagType, int CurrentLevel,int proc_id)
{
    int CurrentNode, n;
    int InsertLevel, InsertNode, InsertOffsetInNode, NoOfInsertItems;
    //PARHEAP Temp[2*MAXITEMS];
    PARHEAP *Temp;
    Temp = (PARHEAP *) MyMalloc(2 * r * sizeof(PARHEAP));
    CurrentNode = LevelFlag[CurrentLevel].Inserts[FlagType].insert_flag;

    if (CurrentNode != -1)
    {
        if (FetchInsertItems(CurrentLevel, FlagType, OddOrEven, &InsertLevel, &InsertNode, &InsertOffsetInNode, &NoOfInsertItems))
        {
            /* Merge current items & insert items, smallest r items go into Current Node */
            mergemin(&partmp[HEAPINDEX(CurrentLevel,CurrentNode,0,r)], r, &partmp[HEAPINDEX(InsertLevel,InsertNode,InsertOffsetInNode,r)], NoOfInsertItems, Temp);
            /* Remaining items become insert items */
            memcpy(&partmp[HEAPINDEX(InsertLevel,InsertNode,InsertOffsetInNode,r)], Temp, NoOfInsertItems * sizeof(PARHEAP) );

            n = InsertLevel - CurrentLevel;
            if ( (Get_Nth_Bit_From_Right(InsertNode, n) == 0) )
                CurrentNode = 2 * CurrentNode;
            else
                CurrentNode = (2 * CurrentNode) + 1;

            if (CurrentLevel <= InsertLevel - 2)
            {
                LevelFlag[CurrentLevel+1].Inserts[FlagType].insert_flag =CurrentNode;
#ifdef PF
                    int LeveltoPF = CurrentLevel+1;
                    if (LeveltoPF < LastLevel1)  
                    {
                        int NodetoPF1 = CurrentNode;
                        //printf("Level %d Node %d\n", LeveltoPF, NodetoPF1);
                        //int proc_id = min(floor((LeveltoPF)/(floor(LastLevel1/M)+1)),floor((LeveltoPF-(LastLevel1%M))/(floor(LastLevel1/M))));
                        //int proc_id = (LeveltoPF % NoOfProcesses)/2;
                        /* Triggering prefetching threads*/ 
                        pthread_mutex_lock(&(pfd[proc_id].mutex));
                        pfd[proc_id].temp[0] = LeveltoPF;
                        pfd[proc_id].temp[1] = NodetoPF1;
                        pthread_cond_signal(&(pfd[proc_id].cond));
                        pthread_mutex_unlock(&(pfd[proc_id].mutex));
                    } 
#endif
                /* Prefetch this node */
                LevelFlag[CurrentLevel+1].Inserts[FlagType].insert_level =InsertLevel;
                LevelFlag[CurrentLevel+1].Inserts[FlagType].insert_offset = (InsertNode*r) + InsertOffsetInNode;
                LevelFlag[CurrentLevel+1].Inserts[FlagType].insert_no_of_items = NoOfInsertItems;
            }
            else
            {
                if (InsertOffsetInNode != 0)
                {
                    PH_Merge(&partmp[HEAPINDEX(InsertLevel,InsertNode,0,r)], InsertOffsetInNode, &partmp[HEAPINDEX(InsertLevel,InsertNode,InsertOffsetInNode,r)].item, NoOfInsertItems, Temp);
                    memcpy(&partmp[HEAPINDEX(InsertLevel, InsertNode, 0,r)], Temp,(InsertOffsetInNode + NoOfInsertItems)*sizeof(PARHEAP) );
                    NoOfLastItems1 = NoOfLastItems1 + NoOfInsertItems;
                }
                else
                {
                    NoOfLastItems1 = NoOfInsertItems;
                    LastNode1++;
                    if (LastNode1 == ldexp(1.0, LastLevel1) )
                    {
                        LastLevel1++;
                        LastNode1 = 0;
                    }
                }
            }
        }
        LevelFlag[CurrentLevel].Inserts[FlagType].insert_flag = -1;  
    }
    free(Temp);
}


/*----------------------------------------------------------------------------
 * Function ........... ParHeapSatisfiedAt
 *
 * Purpose ............ Checks if the parallel heap property is satisfied at
 *                      a specified level and node.
 *
 * Arguments Passed ... CurrentLevel - level at which the heap is to be checked.
 *                      CurrentNode -  node at which the heap is to be checked.
 *
 * Return Value ....... 0 - if parallel heap property is not satisfied
 *                      1 - if parallel heap property is satisfied.
 *
 * Globals Modified ... None
 *---------------------------------------------------------------------------*/
int ParHeapSatisfiedAt(int CurrentLevel, int CurrentNode)
{
#ifdef HDEBUG
    fprintf(stdout, "ParHeapSatist: Enterd function, level = %d, node = %d\n",
            CurrentLevel, CurrentNode);
    PrintParHeap(stdout);
#endif
    if (IsLeafNode(CurrentLevel, CurrentNode))
    {
#ifdef HDEBUG
        fprintf(stdout, "ParHeapSatis: Satisfied because leaf node reached\n");
#endif
        return 1;
    }
#ifdef HDEBUG
    fprintf(stdout, "Heap[%d][%d][%d] = %d, Heap[%d][%d][%d] = %d, Heap[%d][%d][%d] = %d\n", CurrentLevel, CurrentNode, r-1, ParHeap[CurrentLevel][CurrentNode][r-1].item, CurrentLevel+1, 2*CurrentNode, 0, ParHeap[CurrentLevel+1][2*CurrentNode][0].item, CurrentLevel+1, 2*CurrentNode+1, 0, ParHeap[CurrentLevel+1][2*CurrentNode+1][0].item);
#endif
    //if ( (ParHeap[CurrentLevel][CurrentNode][r-1].item <= ParHeap[CurrentLevel+1][2*CurrentNode][0].item) && (ParHeap[CurrentLevel][CurrentNode][r-1].item <= ParHeap[CurrentLevel+1][2*CurrentNode + 1][0].item) )
    if ( (partmp[HEAPINDEX(CurrentLevel,CurrentNode,(r-1),r)].item <= partmp[HEAPINDEX((CurrentLevel+1), (2*CurrentNode), 0, r)].item) && (partmp[HEAPINDEX(CurrentLevel,CurrentNode,(r-1),r)].item <= partmp[HEAPINDEX((CurrentLevel+1),(2*CurrentNode + 1),0,r)].item) )
    {
#ifdef HDEBUG
        fprintf(stdout, "ParHeapSatis: Satisfied before reaching leaf node\n");
#endif
        return 1;
    }
    else
    {
#ifdef HDEBUG
        fprintf(stdout, "ParHeapSatis: Not satisfied\n");
#endif
        return 0;
    }
}


/*----------------------------------------------------------------------------
 * Function ........... AppendToParHeap
 *
 * Purpose ............ Appends the newly created items to the end of the
 *                      parallel heap
 *
 * Arguments Passed ... items - pointer to the array containing the items
 *                      num - number of items to be appended
 *
 * Return Value ....... None
 *
 * Globals Modified ... ParHeap, LevelFlag, LastNode, NoOfLastItems
 *---------------------------------------------------------------------------*/
void AppendToParHeap(PARHEAP *Items, int num)
{
    int offset = 0, ins_count = 0;
    int num1=num;

    /*    fprintf(stdout, "AppendToParHeap: Entered function\n"); */
    /*    fprintf(stdout, "Append: Number of items to be appended = %d\n",num); */
    /*    fprintf(stdout, "Append: Items to be appended = "); */
    /*    PrintPHArray(stdout, Items, num);fprintf(stdout, "\n"); */
    /*    fprintf(stdout, "Append: ParHeap before appending is"); */
    /*    PrintParHeap(stdout); */

    if (NoOfLastItems < r)
    {
        LevelFlag[0].Inserts[ins_count].insert_flag = 0;
        LevelFlag[0].Inserts[ins_count].insert_level = LastLevel;
        LevelFlag[0].Inserts[ins_count].insert_offset= (r*LastNode)+NoOfLastItems;
        /* See if we need new node */
        if (num <= (r - NoOfLastItems) )
        {
            /* We dont need a new node */
            //memcpy(&(ParHeap[LastLevel][LastNode][NoOfLastItems].item), Items, num * sizeof(PARHEAP));
            memcpy(&(partmp[HEAPINDEX(LastLevel,LastNode,NoOfLastItems,r)].item), Items, num * sizeof(PARHEAP));
            NoOfLastItems = NoOfLastItems + num;
            LevelFlag[0].Inserts[ins_count].insert_no_of_items = num;
            return;
        }
        else
        {
            /* We DO need a new node but let us fill the last node first */
            //memcpy(&(ParHeap[LastLevel][LastNode][NoOfLastItems].item), Items, (r - NoOfLastItems)*sizeof(PARHEAP) );
            memcpy(&(partmp[HEAPINDEX(LastLevel,LastNode,NoOfLastItems,r)].item), Items, (r - NoOfLastItems)*sizeof(PARHEAP) );
            offset = r - NoOfLastItems;
            LevelFlag[0].Inserts[ins_count].insert_no_of_items = r - NoOfLastItems;
            num1 = num - (r - NoOfLastItems);
            NoOfLastItems = r;
        }
        ins_count++;
    }
    /* Now NoOfLastItems = r */
    while (1)
    {
        /* See if this is the last node as we need a new level then */
        /*if ((LastNode + 1) == ldexp(1.0, LastLevel) )
            ExpandParHeap();
        else
            LastNode++;
        */
        /* In the new approach to compare PPQ with Seq Heap we allocate the needed memory in advance. This way we skip memory alocation at this stage. */

        if ((LastNode + 1) == ldexp(1.0, LastLevel) )
        {
            LastLevel++;
            LastNode = 0;
        }
        else
        {
            LastNode++;
        }

        if (num1 <= r)
        {
            //memcpy(ParHeap[LastLevel][LastNode], &Items[offset],num1*sizeof(PARHEAP) );
            memcpy(&partmp[HEAPINDEX(LastLevel,LastNode,0,r)], &Items[offset],num1*sizeof(PARHEAP) );
            NoOfLastItems = num-offset;
            LevelFlag[0].Inserts[ins_count].insert_flag = 0;
            LevelFlag[0].Inserts[ins_count].insert_level = LastLevel;
            LevelFlag[0].Inserts[ins_count].insert_offset = LastNode * r;
            LevelFlag[0].Inserts[ins_count].insert_no_of_items = num-offset;
            break;
        }
        else
        {
            //memcpy(ParHeap[LastLevel][LastNode],&Items[offset],r*sizeof(PARHEAP));
            memcpy(&partmp[HEAPINDEX(LastLevel,LastNode,0,r)],&Items[offset],r*sizeof(PARHEAP));
            offset += r;
            num1   -= r;
            LevelFlag[0].Inserts[ins_count].insert_flag = 0;
            LevelFlag[0].Inserts[ins_count].insert_level = LastLevel;
            LevelFlag[0].Inserts[ins_count].insert_offset = LastNode * r;
            LevelFlag[0].Inserts[ins_count].insert_no_of_items = r;
            ins_count++;
        }
    }
}


/*----------------------------------------------------------------------------
 * Function ........... GetSubstituteItems
 *
 * Purpose ............ Gets substitute items from the end of the parallel heap
 *                      to complete r items for the delete-update phase at the
 *                      root.
 *
 * Arguments Passed ... num - number of substitute items required
 *
 * Return Value ....... pointer to array containing the substitute items
 *
 * Globals Modified ... NoOfLastItems
 *---------------------------------------------------------------------------*/
void  GetSubstituteItems(int num,PARHEAP *Items)
{
    int     num1 = 0, store_num = 0;

    store_num = num;
    if (NoOfLastItems >= num)
    {
        //memcpy(Items, &(ParHeap[LastLevel][LastNode][NoOfLastItems-num].item), num*sizeof(PARHEAP));
        memcpy(Items, &(partmp[HEAPINDEX(LastLevel,LastNode,NoOfLastItems-num,r)].item), num*sizeof(PARHEAP));
        NoOfLastItems = NoOfLastItems - num;
        if (NoOfLastItems == 0)
            GoBackByOneNode();
    }
    else
    {
        //memcpy(Items, ParHeap[LastLevel][LastNode], NoOfLastItems*sizeof(PARHEAP));
        memcpy(Items, &partmp[HEAPINDEX(LastLevel,LastNode,0,r)], NoOfLastItems*sizeof(PARHEAP));
        num = num - NoOfLastItems;
        num1 = NoOfLastItems;
        GoBackByOneNode();
        //memcpy(&Items[num1], &(ParHeap[LastLevel][LastNode][NoOfLastItems-num].item), num*sizeof(PARHEAP));
        memcpy(&Items[num1], &(partmp[HEAPINDEX(LastLevel,LastNode,NoOfLastItems-num,r)].item), num*sizeof(PARHEAP));
        NoOfLastItems = NoOfLastItems - num;
    }
    SetLastLevels();
    qsort(Items, store_num, sizeof(PARHEAP), ParHeapCmp);
}


/*----------------------------------------------------------------------------
 * Function ........... GetItemsFromHeap
 *
 * Purpose ............ Returns 1st items from parallel heap structure in an
 *                      integer array.
 *
 * Arguments Passed ... HeapItems - the items in the heap structure
 *                      num - number of heap items
 *
 * Return Value ....... The integer array
 *
 * Globals Modified ... None
 *---------------------------------------------------------------------------*/
int *GetItemsFromHeap(HeapItems, num)
PARHEAP *HeapItems;
int num;
{
    int *Items, i;

    Items = (int *) MyMalloc(num*sizeof(int));

    for ( i=0 ; i < num ; i++ )
        Items[i] = HeapItems[i].item;

    return (Items);
}




/*----------------------------------------------------------------------------
 * Function ........... SetLastLevels
 *
 * Purpose ............ This is called by GetSubstituteItems to set the last
 *                      levels to their right valued after the substitute
 *                      items have been taken away.
 *
 * Arguments Passed ... None
 *
 * Return Value ....... None
 *
 * Globals Modified ... LastLevel1, LastNode1, NoOfLastItems1
 *---------------------------------------------------------------------------*/
void SetLastLevels()
{
    /*   fprintf(stdout, "SetLastLevels: Entered function, globals are\n");
       fprintf(stdout, "LastLevel = %d, LastNode = %d, NoOfLastItems = %d\n",
                        LastLevel, LastNode, NoOfLastItems);
       fprintf(stdout, "LastLevel1 = %d, LastNode1 = %d, NoOfLastItems1 = %d\n",
                        LastLevel1, LastNode1, NoOfLastItems1);
    */
    if (LastLevel1 > LastLevel)
    {
        LastLevel1 = LastLevel;
        LastNode1 = LastNode;
        NoOfLastItems1 = NoOfLastItems;
    }
    else if (LastLevel1 == LastLevel)
    {
        if (LastNode1 > LastNode)
        {
            LastNode1 = LastNode;
            NoOfLastItems1 = NoOfLastItems;
        }
        else if (LastNode1 == LastNode)
        {
            if (NoOfLastItems1 > NoOfLastItems)
                NoOfLastItems1 = NoOfLastItems;
        }
    }
    /*   fprintf(stdout, "SetLastLevels: Exiting function, globals are\n");
       fprintf(stdout, "LastLevel = %d, LastNode = %d, NoOfLastItems = %d\n",
                        LastLevel, LastNode, NoOfLastItems);
       fprintf(stdout, "LastLevel1 = %d, LastNode1 = %d, NoOfLastItems1 = %d\n",
                        LastLevel1, LastNode1, NoOfLastItems1); */
}


/*----------------------------------------------------------------------------
 * Function ........... GoBackByOneNode
 *
 * Purpose ............ Called by GetSubstituteItems if number of substitute
 *                      items required are more than that present in the last
 *                      node
 *
 * Arguments Passed ... None
 *
 * Return Value ....... None
 *
 * Globals Modified ... None
 *---------------------------------------------------------------------------*/
void GoBackByOneNode()
{
    /*    fprintf(stdout, "GoBackByOneNode: Entered function, globals are\n"); */
    /*    fprintf(stdout, "LastLevel = %d, LastNode = %d, NoOfLastItems = %d\n", */
    /*                     LastLevel, LastNode, NoOfLastItems); */
    if (LastNode == 0)
    {
        if (LastLevel == 0)
        {
            fprintf(stdout, "PANIC : Heap is empty !!!\n");
            exit(0);
        }
        LastLevel--;
        LastNode = ldexp(1.0, LastLevel) - 1;
    }
    else
        LastNode--;
    NoOfLastItems = r;
    /*    fprintf(stdout, "GoBackByOneNode: Exiting function, globals are\n"); */
    /*    fprintf(stdout, "LastLevel = %d, LastNode = %d, NoOfLastItems = %d\n", */
    /*                     LastLevel, LastNode, NoOfLastItems); */
}


/*----------------------------------------------------------------------------
 * Function ........... FetchInsertItems
 *
 * Purpose ............ Fetches the insert items for an insert update process
 *
 * Arguments Passed ... CurrentLevel - the level at which the insert update
 *                                     process will take place. The flags at
 *                                     this level are checked to fetch the
 *                                     appropriate insert items
 *                      Flagtype - INSERT_FLAG1 or INSERT_FLAG2
 *                      OddOrEven - Insert at an odd level or even level. If
 *                                  insert is at an even level then a check has
 *                                  to be made to see if insert items exist or
 *                                  they have been taken away by the delete
 *                                  update process at the root.
 *                      THE REMAINING ARGUMENTS ARE CALLED BY REFERENCE
 *                      InsertLevel - Level at which insert items are present
 *                      InsertNode - Node at which insert items are present
 *                      InsertOffsetInNode - Offset in InsertNode where the
 *                                           insert items begin
 *                      NoOfInsertItems - no of insert items required.
 *
 * Return Value ....... 0 - terminate the insert process as all the insert items
 *                          have been taken away by previous update processes
 *                      1 - continue the insert process
 *
 * Globals Modified ... None
 *---------------------------------------------------------------------------*/
int FetchInsertItems(CurrentLevel, FlagType, OddOrEven, InsertLevel,
                     InsertNode, InsertOffsetInNode, NoOfInsertItems)
int CurrentLevel;
int FlagType;
int OddOrEven;
int *InsertLevel;
int *InsertNode;
int *InsertOffsetInNode;
int *NoOfInsertItems;
{
    /** &&& Begin **/
    *InsertLevel = LevelFlag[CurrentLevel].Inserts[FlagType].insert_level;
    *InsertNode = LevelFlag[CurrentLevel].Inserts[FlagType].insert_offset / r;
    *InsertOffsetInNode =
        LevelFlag[CurrentLevel].Inserts[FlagType].insert_offset % r;
    *NoOfInsertItems =
        LevelFlag[CurrentLevel].Inserts[FlagType].insert_no_of_items;
    /* &&& End **/

    /*   fprintf(stdout,
              "Fetch: Level = %d, Node = %d, OffsetInNode  = %d, NoOfItems= %d\n",
              *InsertLevel, *InsertNode, *InsertOffsetInNode, *NoOfInsertItems); */
    if (OddOrEven == EVEN)
    {
        if (LastLevel < *InsertLevel)
            return 0;
        if (LastLevel > *InsertLevel)
            return 1;

        /* Here LastLevel == InsertLevel */
        if (LastNode < *InsertNode)
            return 0;
        if (LastNode > *InsertNode)
            return 1;

        /* Here LastNode == InsertNode */
        if (NoOfLastItems <= *InsertOffsetInNode)
            return 0;
        if (NoOfLastItems >= (*InsertOffsetInNode + *NoOfInsertItems) )
            return 1;
        *NoOfInsertItems = NoOfLastItems - *InsertOffsetInNode;
        /*       fprintf(stdout, "Some insert items taken away\n"); */
        /*       fprintf(stdout, "New NoOfInsertItems = %d, continue insert\n",  */
        /*                        *NoOfInsertItems); */
    }
    return 1;
}


/*----------------------------------------------------------------------------
 * Function ........... IsLeafNode
 *
 * Purpose ............ Checks if the node specified is a leaf node
 *
 * Arguments Passed ... CurrentLevel - level at which node exists
 *                      CurrentNode - the node to be checked.
 *
 * Return Value ....... 0 - not a leaf node
 *                      1 - is a leaf node
 *
 * Globals Modified ... None
 *---------------------------------------------------------------------------*/
int IsLeafNode(CurrentLevel, CurrentNode)
{
    if (CurrentLevel == LastLevel1)
        return 1;
    if ( (CurrentLevel == (LastLevel1 - 1)) && ((2*CurrentNode) > LastNode1) )
        return 1;
    return 0;
}


/*----------------------------------------------------------------------------
 * Function ........... ParGetInsertItems
 *
 * Purpose ............ Gets the new items to be inserted. The item are
 *                      sorted in parallel.
 *
 * Arguments Passed ... InsertItems - the insert items are returned in this array.
 *                      NoOfInsertItems - No of insert items needed
 *                      NoOfProcesses - No of processes forked
 *                      MyId - ID of the process
 *                      Maxval - Maximum value allowed for each item.
 *
 * Return Value ....... void
 *
 * Globals Modified ... NewItems (as NewItems is passed by reference as
 *                                InsertItems)
 *                      Ins_NoOfLastItems
 *---------------------------------------------------------------------------*/
void ParGetInsertItems(PARHEAP *InsertItems, int NoOfInsertItems, int NoOfProcesses, int MyId)
{
    int    NoOfMyItems, StartElem, i, h, NoOfElem, Offset;
    //PARHEAP    Temp[2*MAXITEMS];
    //PARHEAP    MyItems[MAXITEMS];
    PARHEAP    *Temp;
    PARHEAP    *MyItems;
    Temp = (PARHEAP *) MyMalloc( 2 * r * sizeof(PARHEAP));
    MyItems = (PARHEAP *) MyMalloc( r * sizeof(PARHEAP));
    div_t  ans;
    int NoOfProcesses_Orig;
    NoOfProcesses_Orig = NoOfProcesses;
    if (NoOfProcesses > M)
    {
        MyId = MyId - M;
        NoOfProcesses = NoOfProcesses - M;
    }
    ans = div(NoOfInsertItems, NoOfProcesses) ;
    NoOfMyItems = ans.quot ;
    StartElem = (MyId) * NoOfMyItems;
    if ( MyId == (NoOfProcesses - 1) )         /* If my id is last */
        NoOfMyItems += ans.rem;

    Ins_NoOfLastItems = ans.quot + ans.rem;
    Offset = NoOfMyItems;

    //PH_GetNewSortedItems(NoOfMyItems, StartElem,  MAX_ITEM_VALUE, &InsertItems[StartElem]);
    /*Write to a local array first and then vopy the entire array */
    PH_GetNewSortedItems(NoOfMyItems, StartElem,  MAX_ITEM_VALUE, MyItems);
    memcpy(&InsertItems[StartElem], MyItems, NoOfMyItems * sizeof(PARHEAP));

#ifdef HDEBUG
    fprintf(stdout,"ParGetInsertItems: MyId = %d, NoOfMyItems = %d, StartElem = %d, MyItems = ", MyId, NoOfMyItems, StartElem);
    PrintPHArray(stdout, &InsertItems[StartElem], NoOfMyItems);
    fprintf(stdout, "\n");
    fprintf(stdout,"ParGetInsertItems: NewItems = ");
    PrintPHArray(stdout, NewItems, NoOfMyItems);
    fprintf(stdout, "\n");
    fprintf(stdout, "ParGetInsertItems: log = %d\n", ceil_log2(NoOfProcesses));
#endif
    NoOfElem = NoOfProcesses;
    i = MyId + 1;
    if (NoOfProcesses != 1)
    {
        int rc;
        if (NoOfProcesses_Orig > M)
            rc = pthread_barrier_wait(&Worker_Barrier);//Barrier 3 is for P-M 
        else
            rc = pthread_barrier_wait(&Barrier_PMinus1);
    }

    for (h=1 ; h <= ceil_log2(NoOfProcesses) ; h++)
    {
        if ( (NoOfElem % 2) == 0)    // If NoOfElem is even 
        {
            if ( i < NoOfElem/2)
            {
                PH_Merge(&InsertItems[2*i*NoOfMyItems-Offset], NoOfMyItems, &InsertItems[(2*i*NoOfMyItems)-NoOfMyItems-Offset], NoOfMyItems, Temp);
                memcpy(&InsertItems[(2*i*NoOfMyItems)-NoOfMyItems-Offset], Temp, 2*NoOfMyItems*sizeof(PARHEAP));
            }
            else if ( i == NoOfElem/2 )
            {
                PH_Merge(&InsertItems[2*i*NoOfMyItems-Offset], Ins_NoOfLastItems, &InsertItems[(2*i*NoOfMyItems)-NoOfMyItems-Offset], NoOfMyItems, Temp);
                Ins_NoOfLastItems += NoOfMyItems;
                memcpy(&InsertItems[(2*i*NoOfMyItems)-NoOfMyItems-Offset], Temp, (Ins_NoOfLastItems)*sizeof(PARHEAP));
            }
        }
        else
        {
            if ( i <= NoOfElem/2)
            {
                PH_Merge(&InsertItems[2*i*NoOfMyItems-Offset], NoOfMyItems, &InsertItems[(2*i*NoOfMyItems)-NoOfMyItems-Offset], NoOfMyItems, Temp);
                memcpy(&InsertItems[(2*i*NoOfMyItems)-NoOfMyItems-Offset], Temp, (2*NoOfMyItems)*sizeof(PARHEAP));
            }
        }
        if (NoOfProcesses != 1)
        {
            int rc;
            if (NoOfProcesses_Orig > M)
                rc = pthread_barrier_wait(&Worker_Barrier);
            else
                rc = pthread_barrier_wait(&Barrier_PMinus1);
        }

        NoOfMyItems *= 2;
        Offset *= 2;
        NoOfElem = (int) ceil( (double)NoOfElem/2.0 );
    }

#ifdef HDEBUG
    fprintf(stdout,"ParGetInsertItems: InsertItems = ");
    PrintPHArray(stdout, InsertItems, NoOfMyItems);
    fprintf(stdout, "\n");
    fprintf(stdout,"ParGetInsertItems: NewItems = ");
    PrintPHArray(stdout, NewItems, NoOfMyItems);
    fprintf(stdout, "\n");
#endif
    free(Temp); free(MyItems);
}

